package com.cheung.leetcode.stack;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.stack
 * @Author :  cheungming
 * @CreateTime : 2024-06-20 08:39:25
 * @Description : 下一个大元素
 * @Version : 1.0
 */
public class Code496Test {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums1.length];
        Arrays.fill(res, -1);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            // 栈不为空，并且栈顶元素小于当前元素，出栈
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                // 找到nums1中对应的nums2[index]
                int index = stack.pop();
                // 如果nums1中存在nums2[index]
                if (map.containsKey(nums2[index])) {
                    res[map.get(nums2[index])] = nums2[i];
                }
            }
            stack.push(i);
        }

        return res;
    }

    @Test
    public void test1() {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        int[] res = {-1, 3, -1};
        assert Arrays.equals(res, nextGreaterElement(nums1, nums2));
    }

    @Test
    public void test2() {
        int[] nums1 = {2, 4};
        int[] nums2 = {1, 2, 3, 4};
        int[] res = {3, -1};
        assert Arrays.equals(res, nextGreaterElement(nums1, nums2));
    }
}
